# 最直接的解法
class Solution:
    def allCellsDistOrder(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:
        ans = []
        for i in range(R):
            for j in range(C):
                ans.append([i, j])
        ans.sort(key=lambda x: abs(x[0]-r0)+abs(x[1]-c0))
        return ans

# 桶排序
class Solution:
    def allCellsDistOrder(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:
        bocket = collections.defaultdict(list)
        dist = lambda c1, c2 , r1, r2: abs(c1-c2) + abs(r1-r2)
        for i in range(R):
            for j in range(C):
                bocket[dist(j,c0,i,r0)].append([i,j])
        maxdict = max(r0, R-1-r0) + max(c0, C-1-c0)
        ret = []
        for x in range(maxdict+1):  # 注意这里的+1
            ret.extend(bocket[x])
        return ret